package kibahed.university.effizientealgorithmen.algortihms;

import java.util.Collection;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

import kibahed.university.effizientealgorithmen.interfaces.AAlgorithm;

import kibahed.university.effizientealgorithmen.interfaces.*;
import kibahed.university.effizientealgorithmen.standardclasses.EdgeWithCosts;

public class Kruskal extends AAlgorithm {

	PriorityQueue<EdgeWithCosts> queue = new PriorityQueue<EdgeWithCosts>();
	Set<IEdge> minimalSpanningTree = new HashSet<IEdge>();

	int[] parts = null;
	int[] sz = null;

	@SuppressWarnings("unchecked")
	public Kruskal(IGraph graph) {
		setGraph(graph);
		queue.addAll((Collection<? extends EdgeWithCosts>) graph.getEdges());
		parts = new int[graph.getVertexes().length];
		initParts();
		sz = new int[graph.getVertexes().length];
	}

	private void initParts() {
		for (int i = 0; i < parts.length; i++) {
			parts[i] = i;
		}
	}

	private void updateParts(int start, int end) {
		int newEnd = parts[end];
		for (int i = 0; i < parts.length; i++) {
			if (parts[i] == newEnd) {
				parts[i] = parts[start];
			}
		}
	}

	@Override
	public void calculate() {
		System.out.println("STARTING KRUSKAL");
		do {
			IEdge e = queue.remove();
			int start = e.getStart();
			int end = e.getEnd();
			if ((parts[start] != parts[end])) {
				minimalSpanningTree.add(e);
				updateParts(start, end);
			}

		} while (!queue.isEmpty());

		double length = 0;
		for(IEdge e : minimalSpanningTree) {
			length += ((EdgeWithCosts) e).getCost();
		}
		addConsoleText("KRUSKAL");
		addConsoleText("Length of minimal spanning tree = "+length);
		graph.addMessages(getConsoleText());
		graph.setEdgeTour(minimalSpanningTree
				.toArray(new IEdge[minimalSpanningTree.size()]));
		setResult(minimalSpanningTree
				.toArray(new IEdge[minimalSpanningTree.size()]));
	}
}
